/*
 * @Author: your name
 * @Date: 2021-07-05 16:37:17
 * @LastEditTime: 2021-07-05 21:33:41
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /mycode/QuickSort.cpp
 */

#include <iostream>
#include <vector>
using namespace std;
void QuickSort(vector<int> &nums,int l,int r)//这里用的左闭右开，调用形式 也可以写成左闭右闭
{
    if(l>=r)
        return ;
    int first=l;
    int end=r;
    int key=nums[first];
    while(first<end)
    {
        while(first<end && key<=nums[end])
        {
            end--;
        }
        nums[first]=nums[end];
        while(first<end && key>=nums[first])
        {
            first++;
        }
        nums[end]=nums[first];
    }
    nums[first]=key;
    QuickSort(nums,l,first-1);
    QuickSort(nums,first+1,r);
}

void merge_sort(vector<int> &nums, int l, int r, vector<int> &temp) {//节省了空间，浪费了时间
    if (l + 1 >= r) {
return; }
// divide
    int m = l + (r - l) / 2;
    merge_sort(nums, l, m, temp);
    merge_sort(nums, m, r, temp);
// conquer
    int p = l, q = m, i = l;
    while (p < m || q < r) 
    {
        if (q >= r || (p < m && nums[p] <= nums[q])) 
           temp[i++] = nums[p++];
        else 
           temp[i++] = nums[q++];
    }
    for (i = l; i < r; ++i) 
       nums[i] = temp[i];
}

void bubble_sort(vector<int> &v,int n)
{
    for(int i=1;i<n;i++)
    {
        bool flag=false;
        for(int j=1;j<n-i+1;j++)
        {
            if(v[j]<=v[j-1])
            {
                swap(v[j],v[j-1]);
                flag=true;   
            }
        }
        if(!flag)
            break;
    }
}

void selection_sort(vector<int> &nums,int n)
{
    int mid;
    for(int i=0;i<n-1;i++)
    {
        mid=i;
        for(int j=i+1;j<n;++j)
        {
            if(nums[j]<nums[mid])
                mid=j;
        }
        swap(nums[i],nums[mid]);
    }
}

void insertion_sort(vector<int> &nums,int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=i;j>0&&nums[j]<nums[j-1];--j)
            swap(nums[j],nums[j-1]);
    }
}

int main()
{
    vector<int> v{2,3,1,6,4,7,9,8,-9,0};
    //vector<int> v{7,1,4};
    vector<int> t(v);
    int temp;
    /*while(cin>>temp)
    {
        v.push_back(temp);
    }*/
    cout<<"排序之前："<<endl;
    for(auto &a:v)
        cout<<a<<" ";

    //QuickSort(v,0,v.size()-1);
    //merge_sort(v,0,v.size(),t);
    //bubble_sort(v,v.size());
    //selection_sort(v,v.size());
    insertion_sort(v,v.size());
    cout<<endl;
    cout<<"排序之后："<<endl;
    for(auto &a:v)
        cout<<a<<" ";
    cout<<"\n";//不加这一行有百分号
    return 0;
}
